package binaryTree.review;


import binaryTree.TreeNode;

import java.util.LinkedList;
import java.util.Stack;

//3.10
public class Interation2 {

    public void preOrderTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        LinkedList<Integer> list = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while (!st.isEmpty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop();
                if (node.right != null) {
                    st.push(node.right);
                }
                if (node.left != null) {
                    st.push(node.left);
                }
                st.push(node);
                st.push(null);
            } else {
                st.pop();
                node = st.peek();
                st.pop();
                list.add(node.val);
            }
        }
        for (int a :list
             ) {
            System.out.println(a);

        }


    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);

        treeNode1.left=treeNode3;
        treeNode3.left=treeNode2;
        treeNode3.right=treeNode4;


        Interation2 iteration2 = new Interation2();
iteration2.preOrderTraverse(treeNode1);
    }


}
